UVa/11003 - Boxes/11003.2.cpp

   1 /*
   2   Problem: 11003 - Boxes
   3   From the UVa Online Judge
   4
   5   Author: Andrés Mejía-Posada
   6   http://blogaritmo.factorcomun.org
   7
   8   Method: Dynamic programming
   9   Complexity: O(n^2)
  10
  11   Accepted.
  12  */
  13 #include <iostream>
  14 #include <algorithm>
  15
  16 using namespace std;
  17
  18 const int maxBoxes = 1000;
  19 const int maxLoad = 3000;
  20 int dp[maxBoxes][maxLoad+1];
  21 /*
  22   dp[i][j] =  maximum amount of boxes that can be stacked using boxes 0..i (included) such that I can still
  23   add j more weight units on top.
  24  */
  25
  26 int main(){
  27   int n;
  28   while (cin >> n && n){
  29     for (int i=0; i<n; ++i)
  30       for (int j=0; j<=maxLoad; ++j)
  31         dp[i][j] = 0;
  32
  33
  34     for (int i=0; i<n; ++i){
  35       int w, l;
  36       cin >> w >> l; //weight and load of box i-th
  37       for (int j=0; j<= maxLoad; ++j){
  38         if (j <= l) dp[i][j] = 1; //I can stack at least box i-th
  39         //But maybe I can create a bigger stack with the same strength not using box i-th
  40         if (i > 0) dp[i][j] = max(dp[i][j], dp[i-1][j]);
  41
  42         if (j + w <= maxLoad && j <= l && i > 0){ //Now try to add box i-th on top of the previous boxes
  43           dp[i][j] = max(dp[i][j], dp[i-1][j+w]+1);
  44         }
  45       }
  46     }
  47     cout << dp[n-1][0] << endl;
  48   }
  49   return 0;
  50 }